1 using System.Collections.Generic;
2 using UnityEngine;
3
4 namespace ProceduralToolkit
5 {
6 /// <summary>
7 /// Useful utility methods
8 /// </summary>
9 public static class PTUtils
10 {
11 /// <summary>
12 /// Lowercase letters from a to z
13 /// </summary>
14 public const string lowercase = "abcdefghijklmnopqrstuvwxyz";
15
16 /// <summary>
17 /// Uppercase letters from A to Z
18 /// </summary>
19 public const string uppercase = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
20
21 /// <summary>
22 /// Digits from zero to nine
23 /// </summary>
24 public const string digits = "0123456789";
25
26 /// <summary>
27 /// The concatenation of the strings <see cref="lowercase"/> and <see cref="uppercase"/>
28 /// </summary>
29 public const string letters = lowercase + uppercase;
30
31 /// <summary>
32 /// The concatenation of the strings <see cref="letters"/> and <see cref="digits"/>
33 /// </summary>
34 public const string alphanumerics = letters + digits;
35
36 /// <summary>
37 /// Returns point on circle in the XY plane
38 /// </summary>
39 /// <param name="radius">Circle radius</param>
40 /// <param name="angle">Angle in degrees</param>
41 public static Vector2 PointOnCircle2(float radius, float angle)
42 {
43 float angleInRadians = angle*Mathf.Deg2Rad;
44 return new Vector2(radius*Mathf.Sin(angleInRadians), radius*Mathf.Cos(angleInRadians));
45 }
46
47 /// <summary>
48 /// Returns list of points on circle in the XY plane
49 /// </summary>
50 /// <param name="radius">Circle radius</param>
51 /// <param name="segments">Number of circle segments</param>
52 public static List<Vector2> PointsOnCircle2(float radius, int segments)
53 {
54 float segmentAngle = 360f/segments;
55 float currentAngle = 0;
56 var ring = new List<Vector2>(segments);
57 for (var i = 0; i < segments; i++)
58 {
59 ring.Add(PointOnCircle2(radius, currentAngle));
60 currentAngle += segmentAngle;
61 }
62 return ring;
63 }
64
65 /// <summary>
66 /// Returns point on circle in the XY plane
67 /// </summary>
68 /// <param name="radius">Circle radius</param>
69 /// <param name="angle">Angle in degrees</param>
70 public static Vector3 PointOnCircle3XY(float radius, float angle)
71 {
72 float angleInRadians = angle*Mathf.Deg2Rad;
73 return new Vector3(radius*Mathf.Sin(angleInRadians), radius*Mathf.Cos(angleInRadians), 0);
74 }
75
76 /// <summary>
77 /// Returns list of points on circle in the XY plane
78 /// </summary>
79 /// <param name="radius">Circle radius</param>
80 /// <param name="segments">Number of circle segments</param>
81 public static List<Vector3> PointsOnCircle3XY(float radius, int segments)
82 {
83 float segmentAngle = 360f/segments;
84 float currentAngle = 0;
85 var ring = new List<Vector3>(segments);
86 for (var i = 0; i < segments; i++)
87 {
88 ring.Add(PointOnCircle3XY(radius, currentAngle));
89 currentAngle += segmentAngle;
90 }
91 return ring;
92 }
93
94 /// <summary>
95 /// Returns point on circle in the XZ plane
96 /// </summary>
97 /// <param name="radius">Circle radius</param>
98 /// <param name="angle">Angle in degrees</param>
99 public static Vector3 PointOnCircle3XZ(float radius, float angle)
100 {
101 float angleInRadians = angle*Mathf.Deg2Rad;
102 return new Vector3(radius*Mathf.Sin(angleInRadians), 0, radius*Mathf.Cos(angleInRadians));
103 }
104
105 /// <summary>
106 /// Returns list of points on circle in the XZ plane
107 /// </summary>
108 /// <param name="radius">Circle radius</param>
109 /// <param name="segments">Number of circle segments</param>
110 public static List<Vector3> PointsOnCircle3XZ(float radius, int segments)
111 {
112 float segmentAngle = 360f/segments;
113 float currentAngle = 0;
114 var ring = new List<Vector3>(segments);
115 for (var i = 0; i < segments; i++)
116 {
117 ring.Add(PointOnCircle3XZ(radius, currentAngle));
118 currentAngle += segmentAngle;
119 }
120 return ring;
121 }
122
123 /// <summary>
124 /// Returns point on circle in the YZ plane
125 /// </summary>
126 /// <param name="radius">Circle radius</param>
127 /// <param name="angle">Angle in degrees</param>
128 public static Vector3 PointOnCircle3YZ(float radius, float angle)
129 {
130 float angleInRadians = angle*Mathf.Deg2Rad;
131 return new Vector3(0, radius*Mathf.Sin(angleInRadians), radius*Mathf.Cos(angleInRadians));
132 }
133
134 /// <summary>
135 /// Returns list of points on circle in the YZ plane
136 /// </summary>
137 /// <param name="radius">Circle radius</param>
138 /// <param name="segments">Number of circle segments</param>
139 public static List<Vector3> PointsOnCircle3YZ(float radius, int segments)
140 {
141 float segmentAngle = 360f/segments;
142 float currentAngle = 0;
143 var ring = new List<Vector3>(segments);
144 for (var i = 0; i < segments; i++)
145 {
146 ring.Add(PointOnCircle3YZ(radius, currentAngle));
147 currentAngle += segmentAngle;
148 }
149 return ring;
150 }
151
152 /// <summary>
153 /// Returns point on sphere in geographic coordinate system
154 /// </summary>
155 /// <param name="radius">Sphere radius</param>
156 /// <param name="horizontalAngle">Horizontal angle in degrees [0, 360]</param>
157 /// <param name="verticalAngle">Vertical angle in degrees [-90, 90]</param>
158 public static Vector3 PointOnSphere(float radius, float horizontalAngle, float verticalAngle)
159 {
160 return PointOnSpheroid(radius, radius, horizontalAngle, verticalAngle);
161 }
162
163 /// <summary>
164 /// Returns point on spheroid in geographic coordinate system
165 /// </summary>
166 /// <param name="radius">Spheroid radius</param>
167 /// <param name="height">Spheroid height</param>
168 /// <param name="horizontalAngle">Horizontal angle in degrees [0, 360]</param>
169 /// <param name="verticalAngle">Vertical angle in degrees [-90, 90]</param>
170 public static Vector3 PointOnSpheroid(float radius, float height, float horizontalAngle, float verticalAngle)
171 {
172 float horizontalRadians = horizontalAngle*Mathf.Deg2Rad;
173 float verticalRadians = verticalAngle*Mathf.Deg2Rad;
174 float cosVertical = Mathf.Cos(verticalRadians);
175
176 return new Vector3(
177 x: radius*Mathf.Sin(horizontalRadians)*cosVertical,
178 y: height*Mathf.Sin(verticalRadians),
179 z: radius*Mathf.Cos(horizontalRadians)*cosVertical);
180 }
181
182 /// <summary>
183 /// Returns a point on teardrop surface in geographic coordinate system
184 /// </summary>
185 /// <param name="radius">Teardrop radius</param>
186 /// <param name="height">Teardrop height</param>
187 /// <param name="horizontalAngle">Horizontal angle in degrees [0, 360]</param>
188 /// <param name="verticalAngle">Vertical angle in degrees [-90, 90]</param>
189 public static Vector3 PointOnTeardrop(float radius, float height, float horizontalAngle, float verticalAngle)
190 {
191 float horizontalRadians = horizontalAngle*Mathf.Deg2Rad;
192 float verticalRadians = verticalAngle*Mathf.Deg2Rad;
193 float sinVertical = Mathf.Sin(verticalRadians);
194 float teardrop = (1 - sinVertical)*Mathf.Cos(verticalRadians)/2;
195
196 return new Vector3(
197 x: radius*Mathf.Sin(horizontalRadians)*teardrop,
198 y: height*sinVertical,
199 z: radius*Mathf.Cos(horizontalRadians)*teardrop);
200 }
201
202 /// <summary>
203 /// Returns perp of vector
204 /// </summary>
205 /// <remarks>
206 /// Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products."
207 /// Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994
208 /// </remarks>
209 public static Vector2 Perp(Vector2 vector)
210 {
211 return new Vector2(-vector.y, vector.x);
212 }
213
214 /// <summary>
215 /// Returns perp of vector
216 /// </summary>
217 /// <remarks>
218 /// Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products."
219 /// Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994
220 /// </remarks>
221 public static Vector2Int Perp(Vector2Int vector)
222 {
223 return new Vector2Int(-vector.y, vector.x);
224 }
225
226 /// <summary>
227 /// Returns perp dot product of vectors
228 /// </summary>
229 /// <remarks>
230 /// Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products."
231 /// Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994
232 /// </remarks>
233 public static float PerpDot(Vector2 a, Vector2 b)
234 {
235 return a.x*b.y - a.y*b.x;
236 }
237
238 /// <summary>
239 /// Returns perp dot product of vectors
240 /// </summary>
241 /// <remarks>
242 /// Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products."
243 /// Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994
244 /// </remarks>
245 public static int PerpDot(Vector2Int a, Vector2Int b)
246 {
247 return a.x*b.y - a.y*b.x;
248 }
249
250 /// <summary>
251 /// Returns the signed angle in degrees [-180, 180] between from and to
252 /// </summary>
253 /// <param name="from">The angle extends round from this vector</param>
254 /// <param name="to">The angle extends round to this vector</param>
255 public static float SignedAngle(Vector2 from, Vector2 to)
256 {
257 return Mathf.Atan2(PerpDot(to, from), Vector2.Dot(to, from))*Mathf.Rad2Deg;
258 }
259
260 /// <summary>
261 /// Returns the angle in degrees [0, 360] between from and to
262 /// </summary>
263 /// <param name="from">The angle extends round from this vector</param>
264 /// <param name="to">The angle extends round to this vector</param>
265 public static float Angle360(Vector2 from, Vector2 to)
266 {
267 float angle = SignedAngle(from, to);
268 if (angle < 0)
269 {
270 angle += 360;
271 }
272 return angle;
273 }
274
275 /// <summary>
276 /// Returns the signed angle in degrees [-180, 180] between from and to
277 /// </summary>
278 /// <param name="from">The angle extends round from this vector</param>
279 /// <param name="to">The angle extends round to this vector</param>
280 /// <param name="normal">Up direction of the clockwise axis</param>
281 public static float SignedAngle(Vector3 from, Vector3 to, Vector3 normal)
282 {
283 return Mathf.Atan2(
284 Vector3.Dot(normal, Vector3.Cross(from, to)),
285 Vector3.Dot(from, to))*Mathf.Rad2Deg;
286 }
287
288 /// <summary>
289 /// Calculates the linear parameter t that produces the interpolant value within the range [a, b].
290 /// </summary>
291 public static Vector2 InverseLerp(Vector2 a, Vector2 b, Vector2 value)
292 {
293 return new Vector2(
294 Mathf.InverseLerp(a.x, b.x, value.x),
295 Mathf.InverseLerp(a.y, b.y, value.y));
296 }
297
298 /// <summary>
299 /// Calculates the linear parameter t that produces the interpolant value within the range [a, b].
300 /// </summary>
301 public static Vector3 InverseLerp(Vector3 a, Vector3 b, Vector3 value)
302 {
303 return new Vector3(
304 Mathf.InverseLerp(a.x, b.x, value.x),
305 Mathf.InverseLerp(a.y, b.y, value.y),
306 Mathf.InverseLerp(a.z, b.z, value.z));
307 }
308
309 /// <summary>
310 /// Calculates the linear parameter t that produces the interpolant value within the range [a, b].
311 /// </summary>
312 public static Vector4 InverseLerp(Vector4 a, Vector4 b, Vector4 value)
313 {
314 return new Vector4(
315 Mathf.InverseLerp(a.x, b.x, value.x),
316 Mathf.InverseLerp(a.y, b.y, value.y),
317 Mathf.InverseLerp(a.z, b.z, value.z),
318 Mathf.InverseLerp(a.w, b.w, value.w));
319 }
320
321 /// <summary>
322 /// Swaps values of <paramref name="left"/> and <paramref name="right"/>
323 /// </summary>
324 public static void Swap<T>(ref T left, ref T right)
325 {
326 T temp = left;
327 left = right;
328 right = temp;
329 }
330
331 /// <summary>
332 /// Knapsack problem solver for items with equal value
333 /// </summary>
334 /// <typeparam name="T">Item identificator</typeparam>
335 /// <param name="set">
336 /// Set of items where key <typeparamref name="T"/> is item identificator and value is item weight</param>
337 /// <param name="capacity">Maximum weight</param>
338 /// <param name="knapsack">Pre-filled knapsack</param>
339 /// <returns>
340 /// Filled knapsack where values are number of items of type key.
341 /// Tends to overload knapsack: fills remainder with one smallest item.</returns>
342 /// <remarks>
343 /// https://en.wikipedia.org/wiki/Knapsack_problem
344 /// </remarks>
345 public static Dictionary<T, int> Knapsack<T>(Dictionary<T, float> set, float capacity,
346 Dictionary<T, int> knapsack = null)
347 {
348 var keys = new List<T>(set.Keys);
349 // Sort keys by their weights in descending order
350 keys.Sort((a, b) => -set[a].CompareTo(set[b]));
351
352 if (knapsack == null)
353 {
354 knapsack = new Dictionary<T, int>();
355 foreach (var key in keys)
356 {
357 knapsack[key] = 0;
358 }
359 }
360 return Knapsack(set, keys, capacity, knapsack, 0);
361 }
362
363 private static Dictionary<T, int> Knapsack<T>(Dictionary<T, float> set, List<T> keys, float remainder,
364 Dictionary<T, int> knapsack, int startIndex)
365 {
366 T smallestKey = keys[keys.Count - 1];
367 if (remainder < set[smallestKey])
368 {
369 knapsack[smallestKey] = 1;
370 return knapsack;
371 }
372 // Cycle through items and try to put them in knapsack
373 for (var i = startIndex; i < keys.Count; i++)
374 {
375 T key = keys[i];
376 float weight = set[key];
377 // Larger items won't fit, smaller items will fill as much space as they can
378 knapsack[key] += (int) (remainder/weight);
379 remainder %= weight;
380 }
381 if (remainder > 0)
382 {
383 // Throw out largest item and try again
384 for (var i = 0; i < keys.Count; i++)
385 {
386 T key = keys[i];
387 if (knapsack[key] != 0)
388 {
389 // Already tried every combination, return as is
390 if (key.Equals(smallestKey))
391 {
392 return knapsack;
393 }
394 knapsack[key]--;
395 remainder += set[key];
396 startIndex = i + 1;
397 break;
398 }
399 }
400 knapsack = Knapsack(set, keys, remainder, knapsack, startIndex);
401 }
402 return knapsack;
403 }
404 }
405 }
